//
// Created by xili on 2024/8/31 14:57.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int maxSumDivThree(vector<int> &nums) {
        vector<int> dp(3, 0);  // 初始化dp数组，dp[i]表示余数为i的最大和
        for (int num: nums) {
            vector<int> new_dp(dp);
            for (int i: dp) {
                new_dp[(i + num) % 3] = max(new_dp[(i + num) % 3], i + num);
            }
            dp = new_dp;
        }
        return dp[0];  // 返回能被3整除的最大和
    }
};
